home *** CD-ROM | disk | FTP | other *** search
/ Windows Expert / Windows Expert.iso / windownt / uupc11ys.zip / LIB / STRPOOL.C < prev    next >
C/C++ Source or Header  |  1992-12-03  |  10KB  |  292 lines
  1. /*--------------------------------------------------------------------*/
  2. /*    s t r p o o l . c                                               */
  3. /*                                                                    */
  4. /*    String dynamic literal pool management for UUPC/extended        */
  5. /*                                                                    */
  6. /*    Copyright (c) 1992 by Kendra Electronic Wonderworks; all        */
  7. /*    rights reserved except those explicitly granted by the          */
  8. /*    UUPC/extended license.                                          */
  9. /*--------------------------------------------------------------------*/
  10.  
  11. /*
  12.  *    $Id: STRPOOL.C 1.3 1992/12/04 01:00:27 ahd Exp $
  13.  *
  14.  *    $Log: STRPOOL.C $
  15.  * Revision 1.3  1992/12/04  01:00:27  ahd
  16.  * Delete allocating pool message; now handled by pools allocated summary
  17.  *
  18.  * Revision 1.2  1992/12/01  04:37:03  ahd
  19.  * Add SpeedOverMemory
  20.  *
  21.  * Revision 1.1  1992/11/22  20:58:55  ahd
  22.  * Initial revision
  23.  *
  24.  */
  25.  
  26. /*--------------------------------------------------------------------*/
  27. /*                        System include files                        */
  28. /*--------------------------------------------------------------------*/
  29.  
  30. #include <stdio.h>
  31. #include <stdlib.h>
  32. #include <string.h>
  33. #include <limits.h>
  34.  
  35. /*--------------------------------------------------------------------*/
  36. /*                    UUPC/extended include files                     */
  37. /*--------------------------------------------------------------------*/
  38.  
  39. #include "lib.h"
  40.  
  41. /*--------------------------------------------------------------------*/
  42. /*                          Local structures                          */
  43. /*--------------------------------------------------------------------*/
  44.  
  45. typedef struct str_queue {
  46.    struct str_queue *next_link;
  47.    size_t used;
  48.    char pool[BUFSIZ];
  49. }  STR_QUEUE;
  50.  
  51. /*--------------------------------------------------------------------*/
  52. /*                          Local variables                           */
  53. /*--------------------------------------------------------------------*/
  54.  
  55. static STR_QUEUE *anchor = NULL;
  56. static const size_t pool_size = BUFSIZ;
  57. static int pools      = 0;
  58.  
  59. #define _UDEBUG
  60. #ifdef _UDEBUG
  61.  
  62. static int strings    = 0;
  63. static int used       = 0;
  64. static int duplicates = 0;
  65. static int saved      = 0;
  66.  
  67. /*--------------------------------------------------------------------*/
  68. /*                          Local prototypes                          */
  69. /*--------------------------------------------------------------------*/
  70.  
  71. void dump_pool( void );
  72.  
  73. #endif
  74.  
  75. /*--------------------------------------------------------------------*/
  76. /*    The problem:  UUPC/extended allocates large number of small     */
  77. /*    (<< 50 characters) string variables off the heap which are      */
  78. /*    never modified and never deallocated.  This means that the      */
  79. /*    possibly duplicate and relatively large overhead required by    */
  80. /*    malloc and causes these variables to waste space.               */
  81. /*                                                                    */
  82. /*    The solution:  We use this routine to maintain our own local    */
  83. /*    pool of storage for allocating NULL terminated strings out      */
  84. /*    of a chain of large buffers.  This allows us to both reduce     */
  85. /*    storage overhead by placing the strings end to end, and to      */
  86. /*    optionally scan the list for duplicates entries.                */
  87. /*                                                                    */
  88. /*    The duplicate string search can be questionable on a small      */
  89. /*    system, because we have to walk the entire list to locate       */
  90. /*    the duplicate.  However, a smaller system is less likely to     */
  91. /*    have a large dynamic string pool, so we take the hit anyway.    */
  92. /*--------------------------------------------------------------------*/
  93.  
  94. /*--------------------------------------------------------------------*/
  95. /*    s t r p o o l                                                   */
  96. /*                                                                    */
  97. /*    Allocate a string from the string poll                          */
  98. /*--------------------------------------------------------------------*/
  99.  
  100. char *strpool( const char *input , const char *file, size_t line)
  101. {
  102.    int len  = strlen( input );
  103.    int best_fit = SHRT_MAX;
  104.    char *result;
  105.  
  106.    STR_QUEUE *current = anchor;
  107.    STR_QUEUE *last    = anchor;
  108.    STR_QUEUE *save    = NULL;
  109.  
  110. /*--------------------------------------------------------------------*/
  111. /*                      Perform best fit search                       */
  112. /*--------------------------------------------------------------------*/
  113.  
  114.    while(current != NULL )
  115.    {
  116.       int available;
  117.  
  118. /*--------------------------------------------------------------------*/
  119. /*                 Scan current buffer for the string                 */
  120. /*--------------------------------------------------------------------*/
  121.  
  122.       if ( ! bflag[ F_SPEEDOVERMEMORY ] )
  123.       {
  124.          char *target = current->pool;
  125.          char *bufend = target + current->used;
  126.  
  127.          while( target < bufend )
  128.          {
  129.             int target_len = strlen( target );
  130.             int diff =  target_len - len;
  131.  
  132.             if ((diff >= 0 ) && equal( target + diff, input))
  133.             {
  134.  
  135. #ifdef _UDEBUG
  136.                duplicates ++;
  137.                saved += len + 1;
  138. #endif
  139.                return target+diff;
  140.             }
  141.  
  142.             target += target_len + 1;  /* Step to start of next string  */
  143.  
  144.          } /* while( offset < current->used ) */
  145.       }  /* if */
  146.  
  147. /*--------------------------------------------------------------------*/
  148. /*    No string in this buffer, look for best fit in case we need     */
  149. /*    to allocate the string from scratch                             */
  150. /*--------------------------------------------------------------------*/
  151.  
  152.       available = pool_size - current->used;
  153.  
  154.       if (( available < best_fit) && (available > len ))
  155.       {
  156.          best_fit = available;
  157.          save     = current;
  158.       }
  159.       else
  160.          last =  current;        /* Save last buffer in case we
  161.                                     have to chain new buffer in      */
  162.       current = current->next_link;
  163.    }  /* while */
  164.  
  165. /*--------------------------------------------------------------------*/
  166. /*    We have no matching string, we have to insert the new string    */
  167. /*    into our pool                                                   */
  168. /*--------------------------------------------------------------------*/
  169.  
  170.    if ( save == NULL )           /* We find a buffer?                */
  171.    {                             /* No --> Allocate a new one        */
  172.       pools ++;
  173.  
  174.       save = malloc( sizeof *save );
  175.       checkptr(save, file, line);
  176.  
  177.       if ( anchor == NULL )
  178.       {
  179.  
  180. #ifdef _UDEBUG
  181.          atexit( dump_pool );
  182. #endif
  183.  
  184.          anchor = save;
  185.       }
  186.       else
  187.          last->next_link = save;
  188.  
  189.       save->used = 0;
  190.       save->next_link = NULL;
  191.    }
  192.  
  193. /*--------------------------------------------------------------------*/
  194. /*    Save the string, update memory available in current pool,       */
  195. /*    and return to the caller with the new string                    */
  196. /*--------------------------------------------------------------------*/
  197.  
  198.    result = strcpy( save->pool + save->used, input );
  199.    save->used += len + 1;
  200.  
  201. #ifdef _UDEBUG
  202.    strings ++;
  203.    used    += len + 1;
  204. #endif
  205.  
  206.    return result;
  207.  
  208.  } /* strpool */
  209.  
  210. /*--------------------------------------------------------------------*/
  211. /*    s a f e f r e e                                                 */
  212. /*                                                                    */
  213. /*    Insure we are not freeing memory saved for a pool               */
  214. /*--------------------------------------------------------------------*/
  215.  
  216. void safefree( void *input , const char *file, size_t line)
  217. {
  218.    STR_QUEUE *current = anchor;
  219.    int buffers = 0;
  220.    while( current != NULL )
  221.    {
  222.       buffers ++;
  223.       if (( input > (void *) current ) &&
  224.           (input < (void *) (current->pool + pool_size ) ))
  225.       {
  226.          printmsg(0,"Attempt to free string \"%s\" allocated via newstr() in pool %d",
  227.                   input , buffers );
  228.  
  229.          bugout( line, file);
  230.       }
  231.  
  232.       current = current->next_link;
  233.    }
  234.  
  235. #undef free
  236.  
  237.    free(input);
  238.  
  239. } /* safefree */
  240.  
  241. #ifdef _UDEBUG
  242.  
  243. /*--------------------------------------------------------------------*/
  244. /*    d u m  p _ p o o l                                              */
  245. /*                                                                    */
  246. /*    Print the free storage pool                                     */
  247. /*--------------------------------------------------------------------*/
  248.  
  249. void dump_pool( void )
  250. {
  251.  
  252.    STR_QUEUE *current = anchor;
  253.    int buffers = 0;
  254.  
  255.    printmsg(3,"Allocated %d bytes in %d strings "
  256.               "requiring %d pools of %d bytes each",
  257.               used, strings, pools, pool_size );
  258.  
  259.    if ( duplicates )
  260.       printmsg(3,"Saved %d bytes in %d redundant strings",
  261.                saved, duplicates);
  262.  
  263.    if ( debuglevel > 5 )
  264.    while(current != NULL )
  265.    {
  266.       size_t offset = 0;
  267.       size_t strings = 0;
  268.       buffers ++;
  269.  
  270.       printmsg(5,"Buffer %d length is %d bytes",buffers, current->used);
  271.  
  272.       while( offset < current->used )
  273.       {
  274.          size_t target_len = strlen( current->pool + offset );
  275.          strings ++;
  276.          printmsg(5,"[%d,%02d,%02d]=\"%s\"",
  277.                      buffers,
  278.                      strings,
  279.                      target_len,
  280.                      current->pool + offset);
  281.          offset += target_len +1;  /* Go to end of string            */
  282.  
  283.       } /* while( offset < current->used ) */
  284.  
  285.       current = current->next_link;
  286.  
  287.    }  /* while */
  288.  
  289. } /* dump_pool */
  290.  
  291. #endif
  292.